The present invention relates to a buffer memory management system including a set of memory locations, each location temporarily storing a data block (BD) at a respective location address, said system avoiding rearrangement in the event of premature elimination of a data block stored in the memory. The problem of rearrangement following premature elimination of a data block relates to the consequences of that elimination, namely the need to modify the arrangement of the sequential relations between BDs in the management system. This problem is addressed in a previous patent application of the applicant, published under the number FR 2 752 632. The entirety of that application is considered to be incorporated into the present application by reference.
The present invention addresses more particularly the more specific problem of managing locations of a buffer memory when the stored data blocks are managed in accordance with n priority categories (where n is greater than 1), for example hierarchically in categories that reflect the respective priority levels of the various data blocks, and when a data block loss control discipline is used that implies an operation of writing a new data block into a location already occupied by another data block. If the memory is saturated, or filled to a level close to saturation (whether globally or for a given category), that operation typically consists of writing a new data block which has a high priority into a buffer memory location made available by eliminating from it the data block stored in that location, which is generally of lower priority.
This combined operation of eliminating a stored data block and simultaneously writing another data block in the same buffer memory location is referred to hereinafter as xe2x80x9csubstitutionxe2x80x9d; it is also known in the art as xe2x80x9cpush-outxe2x80x9d. Data blocks that can be eliminated are referred to hereinafter as xe2x80x9cdata blocks cleared for eliminationxe2x80x9d (BDCE). They are typically data blocks of nxe2x88x921 lower priority categories (data blocks of the highest category cannot be eliminated).
Apart from the situation of eliminating a data block during a substitution operation, the invention also encompasses two other possible situations of premature elimination (without substitution) of a data block (referred to hereinafter as xe2x80x9cBDxe2x80x9d):
1.) eliminating a cleared for elimination BD in a given category i, typically the BD that is the first in a list used to manage the subset of BDs cleared for elimination (BDCE) of that category i; and
2.) eliminating a particular BD stored in a buffer memory location.
According to the solution proposed in the aforementioned patent application, each BD stored in the buffer memory is associated with a BD identifier (IBD), which can be different from the address (EMT) of its location in the buffer memory, and a BD is eliminated from a location of the buffer memory (EMT) without it being necessary to rearrange the sequential relations between BDs, which are managed by means of their respective BD identifiers (IBD). This is because eliminating a BD immediately frees the buffer memory location (EMT) that it was previously occupying but retains its original data block identifier (IBD). A BD that has been eliminated therefore continues to exist in the management system through its identifier IBD, for example in a chained list, but that identifier IBD is associated with an eliminated BD flag that is detected subsequently when the BD is serviced.
Accordingly, the situation envisaged in the aforementioned patent application is that of premature elimination of a given BD stored in a buffer memory effected as an isolated operation. There may be various causes for isolated elimination of a BD: creation ahead of time of new free locations for possible high-priority BD (typically in the event of imminent saturation of the buffer memory), elimination of an incorrect BD, etc.
Generally speaking, in the buffer memory management system described in the aforementioned patent application, when a BD is eliminated, the memory location (EMT) that it occupies is immediately released so that it become available, but the identifier IBD associated with the BD eliminated in this way is retained, so that the arrangement of the sequential relations between BDs (referenced by their identifier IBD) is not prematurely modified in the management system.
To achieve this technical effect, the management system according to the patent application previously cited includes:
a) free buffer memory location address management means for finding a free location on receiving a new data block to be stored in the buffer memory and for freeing the address of a location when it is no longer occupied by a data block;
b.) write control means for writing a new data block into a location of the buffer memory;
c.) free block identifier management means for assigning a free block identifier to each new data block stored in the buffer memory;
d.) location/block identifier association management means for storing, for each identifier associated with a data block, the address of the location that it occupies in the buffer memory; and
e.) time management means in respect of data blocks stored in the buffer memory, for:
commanding the reception of a new data block to be stored in the buffer memory;
using a given service discipline, arranging the identifiers of the data blocks stored in the buffer memory by managing, as a function of time parameters associated with the identifiers of the blocks, their respective waiting times in the buffer memory and thereby determining respective read times for their service, each data block having normally to be read a predetermined number of times before freeing its location in the buffer memory and its associated block identifier;
commanding service of a data block to be read in the buffer memory; and
possibly commanding premature elimination of a predetermined stored data block, freeing of its location in the buffer memory and temporary preservation of its associated block identifier to prevent rearrangement of time relations between blocks.
To enable premature elimination of a data block stored in a buffer memory location and the immediate release of that location without having to rearrange the block identifiers managed by the time management means, the management system further includes:
a.) elimination flag management means for storing, for each data block identifier, an elimination flag indicating whether the corresponding block has been prematurely eliminated or not;
b.) means for commanding the free location address management means to free the address of the location storing a block to be eliminated;
c.) means for writing into the elimination flag management memory, each time that a block has been eliminated, a flag value storing the elimination of the block;
d.) means for reading the elimination flag management memory in the event of each selection of a block identifier, in order to read that block in the buffer memory, and for authorizing reading the buffer memory location corresponding to the selected block identifier only if the elimination flag that has been read indicates that the block having that block identifier has not already been eliminated; and
e.) means for authorizing the free location address management means to free the address of the location corresponding to a block that has been read after that block has been read a predetermined number of times and for as long as reading is authorized, if that block has not already been eliminated.
With the above management system, it is possible to release a buffer memory location at the earliest possible time because the time management means include means for commanding the free location address management means to free prematurely the address of the location storing the block to be eliminated, as soon as the decision is taken to eliminate that block. The time management means do not rearrange the time parameters when a data block is eliminated, however. They therefore normally select the identifiers of the blocks eliminated without distinguishing them from those of other data blocks. Means are provided for reading elimination flags in the buffer memory to find out if a block identifier designates a block that is still stored. This system does not require any increase in the capacity of the buffer memory.
The aforementioned patent application can therefore be considered to provide a basis for an effective technique for eliminating a given BD stored in the buffer memory without rearranging the sequential relations between BDs (referenced by their identifier IBD) in the management system.
An object of the present invention is to develop the buffer memory management system of the aforementioned patent application in order to retain the same advantages in the particular context where each BD belongs to a category, for example a category reflecting a hierarchical priority level, and when a BD cleared for elimination in a given priority category can be eliminated (as opposed to eliminating a given BD); this kind of elimination operation can be effected in combination with the simultaneous writing of another BD in the same location in the buffer memory because that location has been freed (BD substitution operation). Also, this kind of elimination operation (of a BD cleared for elimination in a given priority category) can equally be effected in isolation.
A BD substitution operation will be considered in a general context, independently of the algorithm used to decide when and in which category this kind of elimination operation is required, and therefore in accordance with any block loss discipline, for example, subject only to the hypothesis that the substitution may be required on receiving a new block to be written in the buffer memory. In other words, a new block received is written:
a.) either normally (without substitution) in a free location of the buffer memory or
b.) by substitution in the buffer memory location previously occupied by the BD eliminated in this substitution operation.
A substitution operation is typically effected in the event of congestion of the buffer memory, i.e. if it is necessary to write a new BD of high priority when no location is available in the buffer memory (whether globally or in the portion of the buffer memory assigned to the priority category of the received new BD). However, some BD loss control disciplines also effect substitution operations ahead of time, even if the buffer memory is not yet completely occupied.
Receiving a BD with substitution therefore necessitates executing in combination, and as fast as for normal reception:
a.) on the one hand, a BD elimination operation consequent upon the previous selection of a BD cleared for elimination in the required priority category (typically corresponding to a priority level lower than that of the received new BD), and
b.) on the other hand, an operation of writing the received new BD in the buffer memory location freed by that elimination (as opposed to a free location in the case of normal BD reception without substitution).
In the above context, the buffer memory management system in accordance with the invention implies, for each category (except the highest category in some applications), managing the BDs stored that belong to the corresponding category and are therefore BDs cleared for elimination, knowing that a block can belong to only one category in the buffer memory.
The management of blocks cleared for elimination is considered in relation to a general substitution operation. In the simplest priority management applications, there are only two BD priority categories (high-priority and low-priority), and there is provision only for the possible elimination of low-priority BDs, in which case it is sufficient to manage a single category of BD cleared for elimination, namely the low-priority BDs. However, the general case will be assumed here, i.e. a plurality of priority categories (n greater than =2), in which case the management system is capable of managing a number C of subsets of BDs cleared for elimination, typically relating to C=nxe2x88x921 priority categories (in most loss disciplines used, the higher priority BDs cannot be eliminated by a substitution operation); however, the situation C=n is equally possible.
Of the n possible priority categories, the indices i and j designate the two categories generally involved in a substitution operation.
Accordingly, in the event of a substitution operation, the BD loss control discipline (which is in itself outside the scope of the invention) determines the required priority category i (from the C subsets of BDs cleared for elimination) in order to effect the elimination. The management system is then informed of that category i, in which it must select a BD cleared for elimination, referred to hereinafter as a BDCE, and the priority category j of the received new BD.
To illustrate the management of BDCE in the event of a substitution operation in the management system in accordance with the invention, note that the latter system,
a. on the one hand, regarding instructions from the BD discipline of the time management means, eliminates a BDCE in the required category i, and
b. on the other hand, takes charge of the received new BD, which belongs to the priority category j and can belong to the highest priority category or another priority category, in which case the received new BD constitutes a new BDCE, which must be added to the subset of BDCE of category j.
Within the function of managing BDCE by category, it is therefore necessary, in the event of BD reception with substitution,
a. on the one hand, to eliminate the BDCE selected for elimination in category i, and
b. on the other hand, possibly to add the received new BD as a BDCE in category j (typically if its priority level j is not the highest level).
Conventionally, j @ i when a BD of higher priority replaces a block of lower priority. However, the situation j=i is not excluded in some sophisticated BD loss disciplines.
For managing the various situations referred to above, the invention proposes a buffer memory management system, each location of said memory being able to store a data block at a location address, and a reference referred to as a data block identifier being associated with each block processed by the system, which system includes:
a.) time management means for data blocks stored in the buffer memory, for commanding reception of a new data block to be stored in the buffer memory; arranging the identifiers of the data blocks stored in the buffer memory in accordance with a given service discipline, by managing, as a function of time parameters associated with the identifiers of said blocks, their respective waiting times in the buffer memory and thereby determining their respective read times for service, each data block having normally to be read a predetermined number of times before freeing its location in the buffer memory and its associated block identifier;
commanding service of a data block to read in the buffer memory; and
possibly commanding premature elimination of a predetermined stored data block, freeing of its location in the memory and temporary preservation of its associated block identifier to prevent rearrangement of the time relations between blocks;
b.) free buffer memory location address management means for searching for a free location address in the event of receiving a new data block to be stored in said buffer memory and freeing the address of a location when it is no longer occupied by a data block;
c.) free data block identifier management means for assigning a free block identifier to each new data block stored in the buffer memory and freeing the identifier associated with a data block when it is no longer used for that block;
d.) write control means for writing a new data block in a location of the buffer memory;
e.) read control means for reading the buffer memory in the event of service of a data block;
f.) location/block identifier association management means for storing, for each identifier associated with a data block, the address of the location that it occupies in the buffer memory; and
g.) elimination flag management means for storing, for each data block identifier, an elimination flag indicating whether the corresponding block has been eliminated prematurely or not, said elimination flag relating to a data block being marked in the event of premature elimination of that block, the presence or absence of said elimination flag relating to a data block being detected in the event of service of that block in order to read it in the buffer memory, reading of said block being authorized only if the elimination flag corresponding to said block identifier indicates that said block has not already been eliminated, and freeing of the address of the location corresponding to said block after said block has been read a predetermined number of times being authorized only if said block has not already been eliminated characterized in that:
1. the stored data blocks are managed in accordance with a plurality of categories, each block belonging to a given category, said system further includes:
i.) category marking management means for storing a category to which each data block belongs; and
ii.) blocks cleared for elimination management means for storing, for each category, a list of the data blocks cleared for elimination belonging to that category; and
2. to enable further the elimination of a data block cleared for elimination from among all the data blocks belonging to a specified category,
i.) said category marking management means effect marking of the category of a data block in the event of reception of a new data block and reading to identify the category of a data block in the event of the last service of a data block that has not already been eliminated or in the event of premature elimination of a predetermined data block; and
ii.) said blocks cleared for elimination management means add, in the event of the reception of a data block, a new data block to the list of data blocks cleared for elimination that corresponds to the priority category of said new block, and delete a data block from its list of data blocks cleared for elimination,
either in the event of the last service of a data block that has not already been eliminated or in the event of premature elimination of a predetermined data block, in which case said block is known and its list corresponds to the category identified for said block by said category marking management means,
or in the event of elimination of a data block cleared for elimination in a specified priority category, in which case said blocks cleared for elimination management means select one of the blocks from the list corresponding to said category and then indicate to said elimination flag management means which block has been selected in order for said means to mark the elimination flag storing the elimination of said block.
The system manages the data blocks cleared for elimination either by means of their data block identifier (IBD) or by means of their location (EMT) in the buffer memory.
In the former case of how the buffer memory management system is used, there can be provision for:
a. the data blocks cleared for elimination management means and the category marking management means to address said data blocks by means of their data block identifier (IBD); and
b. in the event of elimination of a data block cleared for elimination in a specified priority category, the data blocks cleared for elimination management means to transmit the identifier of the data block selected for elimination:
to the location/block identifier association management means, which then determine the corresponding location address occupied by said data block selected for elimination; and
directly as an address of the memory of said elimination flag management means in order for said means to mark the elimination flag storing the elimination of said block.
In the latter case, in which the BD cleared for elimination are managed by means of their location (EMT) in the buffer memory, there can be provision for:
a. the data blocks cleared for elimination management means and the category marking management means to address said data blocks by means of their location address in the buffer memory;
b. the system further to include additional identifier/block location association management means for storing, for each location address (EMT) occupied by a data block in the buffer memory, the identifier (IBD) associated with said block, said identifier being stored at an address corresponding to that of the location occupied by said block in the buffer memory; and
c. in the event of elimination of a data block cleared for elimination in a specified priority category, the data blocks cleared for elimination management means to transmit the location address of the data block selected for elimination to the additional identifier/block location association management means which then determine the corresponding identifier of the data block selected for elimination and then supply said data block identifier as an address of the memory of the elimination flag management means in order for said means to mark the elimination flag storing the elimination of said block.
In the case of managing BDs cleared for elimination by means of their identifiers IBD, there can be provision, for the purposes of isolated elimination of a data block cleared for elimination belonging to a specified data block category, for the location address occupied by the data block selected for elimination, determined by the location/block identifier association management means, to be supplied to the free buffer memory location address management means in order for said means to free the location occupied by said block in the buffer memory. In the case of managing BDs cleared for elimination by means of their locations EMT, there can be provision, for the purposes of isolated elimination of a data block cleared for elimination belonging to a specified data block category, for the location address occupied by the data block selected for elimination by the data blocks cleared for elimination management means to be also supplied directly to the free buffer memory location address management means in order for said means to free the location occupied by said block in the buffer memory.
In one embodiment, for executing a process of reception of a new data block with data block substitution, said process consisting of immediately eliminating a data block cleared for elimination belonging to a specified data block category in order to be able to store the new data block received, there can be provision for:
a. the location address in the buffer memory of the data block eliminated to be used in this case as a free location address for storing the new data block received in the buffer memory, said address being supplied:
to the write control means in order for said means to write the new data block at that location address; and
to the location/block identifier association management means in order for said means to store, for the block identifier assigned to said new data block, the address of the location used to store the data block received;
b. the free data block identifier management means to assign a block identifier to the new data block received and supply that identifier:
to the time management means of the data blocks stored in the buffer memory;
to the location/block identifier association management means in order for said means to store, for the block identifier assigned to said new data block, the address of the location used to store the data block received; and
to the elimination flag management means in order for said means to initialize the elimination flag of the new block received to the non-eliminated state;
c. said category marking management means to mark the category of the new data block received; and
d. the data blocks cleared for elimination management means to add said new data block to the list of data blocks cleared for elimination that corresponds to the priority category of the new data block received.
In the latter case, and if the data blocks cleared for elimination are managed by means of their identifiers IBD, there can be provision for:
a. the free data block identifier management means also to supply the identifier assigned to the data block received:
to the category management means in order for said means to mark the category of the new data block received; and
to the data blocks cleared for elimination management means in order for said means to add said new data block to the list of data blocks cleared for elimination that corresponds to the priority category of the new data block received; and
b. the location address used to store the new block received to be determined by the location/block identifier association management means from the identifier of the block eliminated supplied by the data blocks cleared for elimination management means.
Still in the situation of reception of a new data block with substitution, and when data blocks cleared for elimination are managed by means of their locations EMT in the buffer memory, there can be provision for:
a. the free data block identifier management means also to supply the identifier assigned to the data block received to the additional identifier/block location association management means in order for said means to store, for the buffer memory location in which the new block received is written, its associated identifier; and
b. the location address used to store the new data block received to be selected by the data blocks cleared for elimination management means.
In one advantageous embodiment of the invention, the free data block identifier management means and the location/block identifier association management means use a common memory including a memory line for each possible data block identifier, each line of common memory being used exclusively for one or the other of said two types of management means and containing:
a. either the next block identifier (IBD) in the chained list of free block identifiers if the block identifier corresponding to said common memory line is free and managed by the free data block identifier management means;
b. or the address of the location (EMT) of the buffer memory at which is stored a data block having an associated block identifier corresponding to said common memory line, when said identifier is used and managed by the location/block identifier association management means.
In the case of managing data blocks cleared for elimination by means of their locations EMT in the buffer memory, there can advantageously be provision for the free buffer memory location address management means and the additional identifier/block location association management means to use a common memory including a memory line for each possible location address in the buffer memory, each common memory line being used exclusively by one or the other of said two types of management means and containing:
a. either the next location address in the chained list of free memory locations if the location corresponding to said common memory line is free and managed by the free buffer memory location address management means (GEL);
b. or the block identifier (IBD) associated with a data block stored in the buffer memory at the location address (EMT) corresponding to said common memory line in the event that said location is occupied and managed by the additional identifier/block location association management means.
In the general context of the invention, it is possible to use the chained lists technique to manage the various subsets of data blocks in the system.
Accordingly, there can be provision for the data blocks cleared for elimination management means to manage the various sub-sets of data blocks cleared for elimination using a chained list for each category and for said means to use a common memory including a memory line for each possible data block reference, each line of said common memory being used exclusively by not more than one of said lists for each category and containing the reference of the next block, if any, and the reference of the preceding block, if any, in the chained list of data blocks cleared for elimination corresponding to said category.
In the previous case, and if the data blocks cleared for elimination are managed by means of their data block identifiers, said data blocks references used for addressing said common memory can be data block identifiers.
Similarly, if the data blocks cleared for elimination are managed by means of their buffer memory locations, the data block references used for addressing said common memory can be buffer memory locations.
In the general context of the invention, there can be provision for, in the event of elimination of a data block cleared for elimination in a specified category, the blocks cleared for elimination management means to select the first data block from the list of blocks cleared for elimination corresponding to said specified category.